10785. Сумасшедший нумеролог

 

Нумерология – это наука, которая помогает людям развить свою личность, достичь цели в жизни, набраться опыта. Вычисления в нумерологии бывают как простыми, так и сложными. Например, следующая таблица содержит буквы английского алфавита, каждой из которых поставлено в соответствие некоторое число. Пять букв (A, E, I, O ,U) являются гласными, все остальные – согласными. Буквам A, J и S соответствует значение 1, буквам B, K, T – значение 2 и так далее.

 

\epsfbox{p10785a.eps}

 

При помощи таблицы можно, например, вычислить сумму гласных и согласных букв имени.

 

\epsfbox{p10785b.eps}

 

Нумеролог хочет сгенерировать счастливое имя, которое удовлетворяет следующим условиям:

a) длина имени равна n;

б) сумма гласных и согласных букв минимальна;

в) на нечетных позициях находятся гласные буквы, на четных – согласные. Позиции нумеруются с 1;

г) одна и та же согласная не может повторяться в имени более 5 раз, одна и та же гласная – не более 21 раз;

д) образованное имя должно быть лексикографически наименьшим. Это условие имеет меньший приоритет по сравнению с б).

 

Вход. Первая стока содержит количество тестов N (0 < N £ 250). Далее следует N строк, каждая из которых содержит значение n (0 < n < 211) – длину счастливого имени, которое следует сгенерировать.

 

Выход. Для каждого теста вывести его номер и счастливое имя, удовлетворяющее описанным выше условиям.

 

Пример входа

3

1

5

5

 

Пример выхода

Case 1: A
Case 2: AJAJA
Case 3: AJAJA

 

РЕШЕНИЕ

обработка строк + сортировка

 

Анализ алгоритма

В словаре имеется 5 гласных букв, каждая из которых не может повторяться более 21 раза, а также 21 согласная с повторением не более 5 раз. Таким образом, счастливое имя может содержать не более 5 * 21 + 21 * 5 = 210 букв. В процессе построении имени каждый раз в качестве очередной буквы будем выбирать ту, которая имеет наименьшее значение. То есть на первых 21 нечетных местах будет стоять буква А, на следующих 21 местах – буква U и так далее по возрастанию величин букв. Таким же образом расставляем согласные: первыми 5 буквами на четных местах будут J, следующими – S и так далее.

При перестановке букв на четных или нечетных позициях условия а) – г) остаются инвариантными, но лексикографически можно получать разные имена. Для того чтобы имя было лексикографически наименьшим, после выше описанного построения следует отдельно отсортировать буквы на четных и нечетных местах.

 

Пример

При n = 60 при построении имени получим слово

AJAJAJAJAJASASASASASABABABABABAKAKAKAKAKATUTUTUTUTUCUCUCUCUC

Далее отдельно сортируем буквы на четных и нечетных местах, получая счастливое имя

ABABABABABACACACACACAJAJAJAJAJAKAKAKAKAKASUSUSUSUSUTUTUTUTUT

 

Реализация алгоритма

Занесем гласные и согласные буквы в два массива и расположим их по возрастанию величин:

 

char vowels[5] = {'A','U','E','O','I'};

char cons[21] = {'J','S','B','K','T','C','L','D','M','V',

                 'N','W','F','X','G','P','Y','H','Q','Z','R'};

 

Поскольку счастливое имя содержит не более 210 букв, то будем его сохранять в массиве символов s длины 211 (плюс один нулевой символ в конце строки):

 

char s[211];

 

Введем следующие переменные: p_vowels и p_cons будут содержать индексы текущих гласных и согласных букв соответственно для массивов vowels и cons, переменные num_vowels и num_cons – сколько раз были уже использованы соответственно текущие буквы vowels[p_vowels] и cons[p_cons]. Обнулим описанные переменные:

 

scanf("%d",&N);

for(i = 1; i <= N; i++)

{

  p_vowels = p_cons = 0;

  num_vowels = num_cons = 0;

 

Переменная ptr будет содержать текущую позицию в строке s.

Читаем длину слова n и строим в цикле имя. Нумерация позиций букв по условию задачи начинается с единицы, а в языке С с нуля. Если значение переменной ptr нечетно, то на текущую позицию s[ptr] ставим текущую согласную букву cons[p_cons]. При этом если буква cons[p_cons] уже была использована 5 раз, то следует увеличить индекс p_cons массива согласных букв на единицу, а переменную num_cons обнулить. Если ptr четно, то проделать ту же самую операцию с гласными буквами и переменными, которые за них отвечают.

 

  scanf("%d",&n);

  for(ptr = 0; ptr < n; ptr++)

  {

    if (ptr % 2)

    {

      s[ptr] = cons[p_cons];

      num_cons++;

      if (num_cons == 5)

      {

        num_cons = 0;

        p_cons++;

      }

    } else

    {

      s[ptr] = vowels[p_vowels];

      num_vowels++;

      if (num_vowels == 21)

      {

        num_vowels = 0;

        p_vowels++;

      }

    }

  }

 

Поставим нуль-байт в конце строки s:

 

  s[ptr] = 0;

 

Сортируем гласные буквы:

 

  for(j = 0; j < ptr - 2; j += 2)

    for(k = j + 2; k < ptr; k += 2)

      if (s[j] > s[k]) swap(j,k);

 

Сортируем согласные буквы:

 

  for(j = 1; j < ptr - 2; j += 2)

    for(k = j + 2; k < ptr; k += 2)

      if (s[j] > s[k]) swap(j,k);

 

Выводим результат вместе с номером теста i:

 

  printf("Case %d: %s\n",i,s);

}

 

Функция swap(i, j) переставляет местами символы s[i] и s[j] строки s:

 

void swap(int i, int j)

{

  char temp;

  temp = s[i]; s[i] = s[j]; s[j] = temp;

}